#include <stdio.h>
#include <stdlib.h>

#define M 3  // B+ 树的阶数

// 定义 B+ 树的节点类型
typedef struct BPlusTreeNode {
    int keys[M - 1];                  // 关键字数组，最多存储 M-1 个关键字
    struct BPlusTreeNode* children[M]; // 子节点指针数组，最多有 M 个子节点
    struct BPlusTreeNode* next;        // 叶子节点的指向下一个叶子节点的指针
    int num_keys;                      // 当前关键字个数
    int is_leaf;                       // 是否为叶子节点
} BPlusTreeNode;
// 创建新的 B+ 树节点
BPlusTreeNode* createNode(int is_leaf) {
    BPlusTreeNode* node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));
    node->is_leaf = is_leaf;
    node->num_keys = 0;
    node->next = NULL;
    for (int i = 0; i < M; i++) {
        node->children[i] = NULL;
    }
    return node;
}
// 查找关键字
BPlusTreeNode* search(BPlusTreeNode* root, int key) {
    int i = 0;
    // 找到第一个大于或等于 key 的位置
    while (i < root->num_keys && key > root->keys[i]) {
        i++;
    }

    // 如果是叶子节点，返回叶子节点
    if (root->is_leaf) {
        return root;
    }

    // 否则继续递归到子节点中查找
    return search(root->children[i], key);
}
// 分裂 B+ 树节点
void splitChild(BPlusTreeNode* parent, int i, BPlusTreeNode* child) {
    // 创建一个新节点来存储 child 的后半部分
    BPlusTreeNode* newChild = createNode(child->is_leaf);
    newChild->num_keys = M / 2;

    // 将 child 的后半部分关键字复制到新节点
    for (int j = 0; j < M / 2; j++) {
        newChild->keys[j] = child->keys[j + M / 2];
    }

    // 如果不是叶子节点，也要复制子节点指针
    if (!child->is_leaf) {
        for (int j = 0; j <= M / 2; j++) {
            newChild->children[j] = child->children[j + M / 2];
        }
    }

    // 缩减 child 中的关键字数
    child->num_keys = M / 2;

    // 将新节点插入到父节点的子节点中
    for (int j = parent->num_keys; j >= i + 1; j--) {
        parent->children[j + 1] = parent->children[j];
    }
    parent->children[i + 1] = newChild;

    // 将中间关键字上移到 parent 中
    for (int j = parent->num_keys - 1; j >= i; j--) {
        parent->keys[j + 1] = parent->keys[j];
    }
    parent->keys[i] = child->keys[M / 2];
    parent->num_keys++;
}
// 在非满节点中插入关键字
void insertNonFull(BPlusTreeNode* node, int key) {
    int i = node->num_keys - 1;

    // 如果是叶子节点，直接插入到合适的位置
    if (node->is_leaf) {
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->num_keys++;
    } else {
        // 找到合适的子节点递归插入
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;

        // 如果子节点满了，先分裂再插入
        if (node->children[i]->num_keys == M - 1) {
            splitChild(node, i, node->children[i]);
            if (key > node->keys[i]) {
                i++;
            }
        }
        insertNonFull(node->children[i], key);
    }
}

// 插入关键字到 B+ 树
void insert(BPlusTreeNode** root, int key) {
    BPlusTreeNode* r = *root;

    // 如果根节点满了，需要分裂
    if (r->num_keys == M - 1) {
        BPlusTreeNode* newRoot = createNode(0);  // 新建一个根节点
        newRoot->children[0] = r;
        splitChild(newRoot, 0, r);  // 分裂原根节点
        insertNonFull(newRoot, key);  // 插入关键字
        *root = newRoot;  // 更新根节点
    } else {
        insertNonFull(r, key);
    }
}
// 中序遍历 B+ 树
void inorderTraversal(BPlusTreeNode* root) {
    if (root == NULL) {
        return;
    }

    int i;
    for (i = 0; i < root->num_keys; i++) {
        if (!root->is_leaf) {
            inorderTraversal(root->children[i]);
        }
        printf("%d ", root->keys[i]);
    }

    if (!root->is_leaf) {
        inorderTraversal(root->children[i]);
    }
}
int main() {
    BPlusTreeNode* root = createNode(1);  // 创建一个空的 B+ 树

    // 插入一些关键字
    insert(&root, 10);
    insert(&root, 20);
    insert(&root, 5);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 30);
    insert(&root, 7);
    insert(&root, 17);

    // 中序遍历 B+ 树
    printf("Inorder traversal of the B+ tree:\n");
    inorderTraversal(root);
    printf("\n");

    // 查找关键字
    BPlusTreeNode* result = search(root, 6);
    if (result != NULL) {
        printf("Found key 6 in B+ tree\n");
    } else {
        printf("Key 6 not found in B+ tree\n");
    }

    return 0;
}
